/*
    Created by Pujx on 2024/3/17.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
// #define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n)                                                           \
  for (int i = 1; i <= n; i++)                                                 \
  cin >> a[i]
#define cinstl(a)                                                              \
  for (auto &x : a)                                                            \
    cin >> x;
#define coutarr(a, n)                                                          \
  for (int i = 1; i <= n; i++)                                                 \
  cout << a[i] << " \n"[i == n]
#define coutstl(a)                                                             \
  for (const auto &x : a)                                                      \
    cout << x << ' ';                                                          \
  cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
// #include "debug.h"
#else
#define dbg(...) void(0)
#endif

const int N = 1e5 + 5;
// const int M = 1e5 + 5;
const int mod = 998244353;
// const int mod = 1e9 + 7;
// template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a *
// a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; } template <typename
// T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b
// >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int w[N][10];
int n, m, t, k, q;
map<int, int> mp[N];
struct edge {
  int u, v;
  vector<vector<int>> w;
} es[N];
int del[N], in[N];

void work() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < k; j++)
      cin >> w[i][j];
  for (int i = 0; i < m; i++) {
    auto &e = es[i];
    cin >> e.u >> e.v;
    e.w.assign(k, vector<int>(k));
    for (auto &v : e.w)
      for (auto &x : v)
        cin >> x;
    mp[e.u][e.v] = i;
    mp[e.v][e.u] = i;
    ++in[e.u], ++in[e.v];
  }

  queue<int> q;
  for (int i = 0; i < n; i++)
    if (in[i] <= 2)
      q.push(i);
  while (!q.empty()) {
    auto transposi = [&](auto &e) {
      swap(e.u, e.v);
      for (int i = 0; i < k; i++)
        for (int j = i + 1; j < k; j++)
          swap(e.w[i][j], e.w[j][i]);
    };
    auto del1 = [&](int u) {
      assert(mp[u].size() == 1);
      int v = mp[u].begin()->first;
      auto &e = es[mp[u].begin()->second];
      if (u == e.v)
        transposi(e);
      for (int j = 0; j < k; j++) {
        int mn = inf;
        for (int i = 0; i < k; i++)
          mn = min(mn, e.w[i][j] + w[u][i]);
        w[v][j] += mn;
      }
      del[u] = 1;
      mp[u].clear();
      mp[v].erase(u);
      if (--in[v] <= 2)
        q.push(v);
    };
    auto del2 = [&](int u) {
      assert(mp[u].size() == 2);
      int v1 = mp[u].begin()->first, v2 = mp[u].rbegin()->first;
      auto &e = mp[v1].count(v2)
                    ? es[mp[v1][v2]]
                    : (++in[v1], ++in[v2],
                       es[mp[v1][v2] = mp[v2][v1] = m++] = {
                           v1, v2, vector<vector<int>>(k, vector<int>(k, 0))});
      if (v1 == e.v)
        swap(v1, v2);
      auto &e1 = es[mp[u][v1]], &e2 = es[mp[u][v2]];
      if (u == e1.v)
        transposi(e1);
      if (u == e2.v)
        transposi(e2);
      for (int j = 0; j < k; j++)
        for (int l = 0; l < k; l++) {
          int mn = inf;
          for (int i = 0; i < k; i++)
            mn = min(mn, e1.w[i][j] + e2.w[i][l] + w[u][i]);
          e.w[j][l] += mn;
        }
      del[u] = 1;
      mp[u].clear();
      mp[v1].erase(u), mp[v2].erase(u);
      if (--in[v1] <= 2)
        q.push(v1);
      if (--in[v2] <= 2)
        q.push(v2);
    };

    int u = q.front();
    q.pop();
    if (del[u])
      continue;
    if (in[u] == 0)
      break;
    else if (in[u] == 1)
      del1(u);
    else
      del2(u);
  }

  vector<int> vv;
  vector<edge> ee;
  for (int i = 0; i < n; i++)
    if (!del[i])
      vv.emplace_back(i);
  for (int i = 0; i < m; i++)
    if (!del[es[i].u] && !del[es[i].v])
      ee.push_back({lower_bound(all(vv), es[i].u) - vv.begin(),
                    lower_bound(all(vv), es[i].v) - vv.begin(), es[i].w});
  int nn = vv.size(), mm = ee.size();
  int ans = inf;
  vector<int> sel(nn);
  function<void(int, int)> dfs = [&](int i, int sum) {
    if (i == nn) {
      int tem = sum;
      for (int j = 0; j < mm; j++)
        tem += ee[j].w[sel[ee[j].u]][sel[ee[j].v]];
      ans = min(ans, tem);
      return;
    }
    for (int j = 0; j < k; j++) {
      sel[i] = j;
      dfs(i + 1, sum + w[vv[i]][j]);
    }
  };
  dfs(0, 0);
  cout << ans << endl;
}

signed main() {
#ifdef LOCAL
  freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
  freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int Case = 1;
  // cin >> Case;
  while (Case--)
    work();
  return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/
